Benvenuti alla Lezione 3 di Concetti di Intelligenza Artificiale (PolyU COMP5511). In questa sessione, passiamo dal pathfinding di agenti singoli alla Ricerca Avversaria, in cui gli agenti operano in ambienti multi-agente competitivi. Introduciamo anche i Problemi di Soddisfacimento di Vincoli (CSP), un paradigma in cui l'obiettivo è trovare uno stato che soddisfi un insieme specifico di restrizioni piuttosto che un percorso.
Concetti Chiave
- Ricerca Avversaria: Si concentra su algoritmi come Minimax e Potatura Alpha-Beta per prendere decisioni razionali contro un avversario intelligente.
- Monte Carlo Tree Search (MCTS): Esplora il processo decisionale probabilistico, fungendo da spina dorsale per le moderne IA di gioco come AlphaGo.
- Soddisfacimento di Vincoli: Modella problemi utilizzando Variabili, Domini e Vincoli, risolti tramite Backtracking e Ricerca Locale.
Analisi della Complessità
Nelle impostazioni avversarie, la complessità dello spazio di ricerca è spesso definita dal fattore di diramazione del gioco
Avviso di Cambio di Paradigma
A differenza della ricerca standard (ad es. A* o BFS) in cui l'ambiente è statico, Ricerca Avversaria presuppone che l'ambiente (l'avversario) cerchi attivamente di minimizzare il tuo successo. Nei CSP, l'ordine delle azioni conta meno della validità dell'assegnazione finale.
Pseudocodice Concettuale: Tipi di Agente
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).